/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓CS206␈↓ ¬TMIDTERM EXAMINATION␈↓ 
lFALL 1983 

␈↓ α∧␈↓␈↓ αTThis␈α
examination␈α∞is␈α
open␈α
book␈α∞and␈α
notes.␈α∞ Write␈α
LISP␈α
functions␈α∞or␈α
predicates␈α∞as␈α
follows
␈↓ α∧␈↓except␈α⊂where␈α⊂something␈α⊂else␈α⊂is␈α⊂requested.␈α⊃ Either␈α⊂notation␈α⊂may␈α⊂be␈α⊂used.␈α⊂ Equal␈α⊂credit␈α⊃for␈α⊂all
␈↓ α∧␈↓problems.

␈↓ α∧␈↓␈↓ αT1.␈α
␈↓↓odds␈α
u␈↓␈α
is␈α
the␈α
sequence␈α
of␈α
odd␈α
numbered␈α
elements␈α
of␈α
the␈α
list␈α
␈↓↓u.␈↓␈α
Likewise␈α
␈↓↓evens u␈↓␈α
is␈α
the
␈↓ α∧␈↓sequence␈α∨of␈α∨even␈α∨numbered␈α∨elements␈α∨of␈α∨␈↓↓u.␈↓␈α∨Thus␈α∨␈↓↓odds ␈↓ (A B C D E) = (A C E),␈α≡and
␈↓ α∧␈↓␈↓↓evens ␈↓(A B C D E) = (B D).␈α ␈↓↓combine[u,v]␈↓␈αis␈αthe␈αresult␈αof␈αinterleaving␈αelements␈αof␈α␈↓↓u␈↓␈αand␈α␈↓↓v␈↓␈αtaking
␈↓ α∧␈↓one␈α⊂from␈α⊂each␈α⊂in␈α⊂turn␈α⊂starting␈α⊂with␈α⊂␈↓↓u␈↓␈α⊂and␈α⊂putting␈α⊂any␈α⊂left␈α⊂over␈α⊂elements␈α⊂at␈α⊂the␈α⊃end.␈α⊂ Thus
␈↓ α∧␈↓␈↓↓combine␈↓[(A C E),(B D)] = (A B C D E).

␈↓ α∧␈↓␈↓ αT2.␈αConsider␈αconditional␈αexpressions␈α␈↓↓(if p a b)␈↓,␈αwhere␈αany␈αof␈α␈↓↓p,␈↓␈α␈↓↓a␈↓␈αand␈α␈↓↓b␈↓␈αmay␈αbe␈αconditional
␈↓ α∧␈↓expressions.␈α If␈αany␈α␈↓↓p␈↓␈αis␈α␈↓↓T␈↓␈αor␈α␈↓↓F,␈↓␈αthe␈αexpression␈αmay␈αbe␈αsimplified.␈α Moreover,␈αany␈αoccurrence␈αof
␈↓ α∧␈↓␈↓↓p␈↓␈αin␈α␈↓↓a␈↓␈αmay␈αbe␈αreplaced␈αby␈α␈↓↓T␈↓␈αand␈αany␈α
occurrence␈αof␈α␈↓↓p␈↓␈αin␈α␈↓↓b␈↓␈αmay␈αbe␈αreplaced␈αby␈α␈↓↓F.␈↓␈α
␈↓↓ifsimp exp␈↓␈αis
␈↓ α∧␈↓the␈α
result␈α
of␈α
applying␈α
these␈α
simlifications␈α
to␈α
␈↓↓exp␈↓␈α
and␈α
its␈α
subexpressions␈α
until␈α
they␈α
can␈α
no␈αlonger␈α
be
␈↓ α∧␈↓applied.

␈↓ α∧␈↓␈↓ αT3. Prove that for all S-expressions ␈↓↓x␈↓ and ␈↓↓z␈↓ and atoms ␈↓↓y␈↓,

␈↓ α∧␈↓␈↓ αT␈↓↓subst[x,y,subst[x,y,z]] = subst[subst[x,y,x],y,z]␈↓.

␈↓ α∧␈↓␈↓↓subst␈↓,␈α
which␈α
substitutes␈α
the␈α
S-expression␈α
␈↓↓x␈↓␈α
for␈α
each␈α
occurrence␈α
of␈α
the␈α
atom␈α
␈↓↓y␈↓␈α
in␈α
the␈αS-expression␈α
␈↓↓z␈↓
␈↓ α∧␈↓is defined by

␈↓ α∧␈↓␈↓ αT␈↓↓subst[x,y,z] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t z ␈↓αthen␈↓↓ [␈↓αif␈↓↓ z = y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ z] ␈↓αelse␈↓↓ subst[x,y,␈↓αa␈↓↓ z].subst[x,y,␈↓αd␈↓↓ z]␈↓.

␈↓ α∧␈↓Be sure and indicate the ␈↓	F␈↓ used in the induction.

␈↓ α∧␈↓␈↓ αT4.␈α∩Prove␈α∩␈↓↓∀u.combine(odds u,evens u) = u␈↓,␈α⊃where␈α∩the␈α∩functions␈α⊃were␈α∩those␈α∩of␈α∩problem␈α⊃1.
␈↓ α∧␈↓Hint:␈α
Depending␈α
on␈α
how␈α
you␈α
write␈α
the␈α
functions,␈α
you␈α
may␈α
be␈α
able␈α
to␈α
use␈α
list␈α
induction␈α
or␈αyou␈α
may
␈↓ α∧␈↓have␈α∞to␈α∞use␈α∞rank␈α∞induction.␈α∞ Be␈α∞sure␈α∞to␈α∞state␈α∞the␈α∞induction␈α∞principle␈α∞used␈α∞and␈α∞define␈α∞both␈α
the
␈↓ α∧␈↓rank function (if any) and the ␈↓	F␈↓ used in the induction.  The schema for rank induction is

␈↓ α∧␈↓␈↓↓[∀x.[∀y.rank y < rank x ⊃ ␈↓	F␈↓↓(y)] ⊃ ␈↓	F␈↓↓(x)] ⊃ ∀x.␈↓	F␈↓↓(x)␈↓.